#ifndef DTAHASH_H_INCLUDED
#define DTAHASH_H_INCLUDED


//Estrutura do hash
//------------------------------------------------------------------------------
/*
[H]
|K0;3| -> |dt0| -> |dt1| -> |dt2| ->//
|K1;1| -> |dt0| ->//
|K2;2| -> |dt0| -> |dt1| ->//
|K3;4| -> |dt0| -> |dt1| -> |dt2| -> |dt3| ->//
|K4;0| ->//
 .
 .
 .
|Kn-1;1| -> |dt0| ->//
[/H]

Onde:
[kw;j] : w=> id dado pela funcao de hash
         j=> numero de resgistros na estrutura

 * A largura do hash (sizeHash) eh por padrao definida como 1000 com o construtor
 * padrao. Um hash mais largo eh definido com o uso do construtor onde passa-se
 * como parametro a largura do hash. É aconselhavel por razoes de eficiencia,
 * manter um hash com largura de pelo menos 7% do total de chaves; aplicacoes
 * onde o numero de chaves é desconhecido, deve-se manter um hash mais largo, afim
 * de evitar um grande numero de colisoes (mais que 700)
 *
 * É obrigatorio que o tipo de dado tratado tenha um método chamado "toHash"
 * que mapeia o dado em uma das posicoes da tabela hash. Uma má implementacao
 * deste metodo, implica em grande colisao na tabela hash, fazendo que haja perda
 * de desempenho. Veja um exemplo da implementacao deste método na classe DTAPonto.
*/

//------------------------------------------------------------------------------


#include <vector>
#include "DTALinkedList.h"


//hash onde a colisao eh tratada com listas encadeadas
template<class tipoData>
struct strNodeHash
{
    int numReg; //numero de registros no apontador
    DTALinkedList<tipoData> *pont; //lista encadeada para armazenar os dados
};

template<class tipoData>
class DTAHash
{

    public:
    typedef  strNodeLinkedList<tipoData> HashNode; //ponteiro para um nó adicionado
    typedef  strNodeLinkedList<tipoData> *ptrHashNode; //ponteiro para um nó adicionado

    DTAHash();
    DTAHash(int rangeHash);                 //construtor que seta a largura do hash;
                                            //Por razao de eficiencia eh aconselhavel manter no minimo a largura de 7% dos numero de chaves

    ~DTAHash();
    void setHashSize();                     //largura do hash; O valor padrao é 1000.
                                            //Por razões de eficiencia, é aconselhável manter um hash com largura de 7% do número
                                            //total de chaves que serao inseridas.
                                            //se o número de chaves nao eh certo, deve-se fazer uma estimativa.
                                            //Hash pouco com restricao de largura => em maior numero de colisoes => perda de eficiencia.
    
    const HashNode* addData(tipoData dt);   //este método insere um elemento na estrutura, retornando o ponteiro onde foi inserido.
                                            //note que o retorno é const; isso significa que o ponteiro serve para apenas lermos os dados.
                                            //qualquer alteracao deve ser feita através do método update, fornecido nessa mesam classe
                                            //Note que dados repetidos sao insridos apenas uma vez.
    bool removeData(tipoData dt);           //remove um elemento da estrura

    bool findData(tipoData dt);              //procura se um dado esta inserido na estrutura

    bool updateData(tipoData oldData, tipoData newData); //atualiza os valores de um dado, que esta presente na estrutura

    HashNode* alterProperty(tipoData dt);   //retorna um ponteiro ao dado, sendo que apenas os atributos que nao interferem no
                                            //cálculo do hash devem ser alterados; caso se altere os atributos do hash, a consistencia de toda a estrutura
                                            //será comprometida

    void printHashHeight();
    
    private:
    int sizeHash; //tamanho do hash
    strNodeHash<tipoData> *vetHash; //vetor que contem ponteiros para as estruturas que armazenam os dados
    
};

template<class tipoData>
DTAHash<tipoData>::DTAHash()
{
    register int i;
    vetHash = new  strNodeHash<tipoData>[1000];
    sizeHash = 1000;

    for(i=0;i<1000;i++)
        vetHash[i].pont = new DTALinkedList<tipoData>;
};

template<class tipoData>
DTAHash<tipoData>::DTAHash(int rangeHash)
{
    register int i;
    vetHash = new  strNodeHash<tipoData>[rangeHash];
    sizeHash = rangeHash;

    for(i=0;i<rangeHash;i++)
        vetHash[i].pont = new DTALinkedList<tipoData>;
};

template<class tipoData>
DTAHash<tipoData>::~DTAHash()
{
    delete vetHash;
}

template<class tipoData>
const strNodeLinkedList<tipoData> *DTAHash<tipoData>::addData(tipoData dt)
{
    int id;
    const  strNodeLinkedList<tipoData> *ret;
    bool inserido = false;
    
    id = dt.toHash(sizeHash); // o método toHash deve estar implementado na classe que esta instanciando o hash e deve retornar um inteiro
    ret = NULL;

   // cout << "id da lista: " << id << endl;
    
    //procura se o dado ja nao esta presente na estrutura
    inserido = vetHash[dt.toHash(sizeHash)].pont->findData(dt);

  //  cout << "insrido: " << inserido << endl;

    if( inserido == false)
    {
        ret = vetHash[dt.toHash(sizeHash)].pont->addData(dt);
        vetHash[dt.toHash(sizeHash)].numReg++;
        //cout << "inserindo novo" <<endl;
    }
    else
    {
        ret = vetHash[dt.toHash(sizeHash)].pont->findPointer(dt);
        //cout << "ja estava inserido " << endl;
    }

    return ret;
   
};

template<class tipoData>
bool DTAHash<tipoData>::removeData(tipoData dt)
{
    int id;
    bool inserido = false;
    id = dt.toHash(sizeHash); // o método toHash deve estar implementado na classe que esta instanciando o hash e deve retornar um inteiro

    //procura se o dado ja nao esta presente na estrutura
    inserido = vetHash[dt.toHash(sizeHash)].pont->findData(dt);

    if( inserido == true)
    {
        vetHash[dt.toHash(sizeHash)].pont->removeData(dt);
        vetHash[dt.toHash(sizeHash)].numReg--;
        return true;
    }
    else
        return false;

};

template<class tipoData>
bool DTAHash<tipoData>::findData(tipoData dt)
{
    register int i;
    //cout << " procurando em DTAHash: " ;
   // dt.print();

    //for(i=0;i<)
    //cout << "Valor do numero deelementos: " <<(vetHash[dt.toHash(sizeHash)]).pont->getNumReg() << endl;

    //cout <<"Valor gerado do hash: "<<dt.toHash(sizeHash) << endl;
    return (vetHash[dt.toHash(sizeHash)]).pont->findData(dt);
}

template<class tipoData>
bool DTAHash<tipoData>::updateData(tipoData oldData, tipoData newData)
{
    bool dataRemovida;
    dataRemovida = removeData(oldData);
    if (  dataRemovida== true)
    {
        addData(newData);
        return true;
    }
    else
    return false;
}

template<class tipoData>
strNodeLinkedList<tipoData> * DTAHash<tipoData>::alterProperty(tipoData dt)
{
    if((vetHash[dt.toHash(sizeHash)]).pont->findData(dt) == true )
        return (vetHash[dt.toHash(sizeHash)]).pont->findPointer(dt);
    else
        return NULL;
}


template<class tipoData>
void DTAHash<tipoData>::printHashHeight()
{
    register int i;

    cout << endl << endl;
    for(i=0;i<sizeHash;i++)
        cout << vetHash[i].numReg << endl;
}

//---------------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------ESPECIFICACAO DO TEMPLATE PARA INTEIROS
/*
template<>
const DTAHash<int>::HashNode* DTAHash<int>::addData(int dt)
{
    int id;
    bool inserido = false;
    const  strNodeLinkedList<int> *ret;
    ret =NULL;

  //  id = dt.toHash(sizeHash); // o método toHash deve estar implementado na classe que esta instanciando o hash e deve retornar um inteiro

   // cout << "id da lista: " << id << endl;

    //procura se o dado ja nao esta presente na estrutura
    inserido = vetHash[dt%sizeHash].pont->findData(dt);

  //  cout << "insrido: " << inserido << endl;

    if( inserido == false)
    {
        ret = vetHash[dt%sizeHash].pont->addData(dt);
        vetHash[dt%sizeHash].numReg++;
    }

    return ret;

};

template<>
bool DTAHash<int>::finData(int dt)
{
    return (vetHash[dt%sizeHash]).pont->findData(dt);
}


template<>
bool DTAHash<int>::removeData(int dt)
{
    int id;
    bool inserido = false;
  //  id = dt.toHash(sizeHash); // o método toHash deve estar implementado na classe que esta instanciando o hash e deve retornar um inteiro

    //procura se o dado ja nao esta presente na estrutura
    inserido = vetHash[dt%sizeHash].pont->findData(dt);

    if( inserido == true)
    {
        vetHash[dt%sizeHash].pont->removeData(dt);
        vetHash[dt%sizeHash].numReg--;
        return true;
    }
    else
        return false;

};

//------------------------------------------------------------------------------FIM DA ESPECIFICACAO PARA INTEIROS
//----------------------------------------------------------------------------------------------------------------
*/
#endif // DTAHASH_H_INCLUDED
